package util;

import graph.GraphFile;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import testbench.Driver;

/**
 * Depth-first search static functions.
 * 
 * @author Jonathan
 * 
 */
public class DFS
{
    private static HashMap<Integer, Boolean> marked;
    private static HashMap<Integer, Integer> edgeTo;
    private static GraphFile g;

    /**
     * Traverse n levels deep from v1 and v2 and find the pages that are in common at those levels.
     * 
     * @param g
     *            GraphFile object
     * @param v1
     *            First starting page
     * @param v2
     *            Second starting page
     * @param level
     *            Levels to traverse
     * @return LinkedList of common pages at the nth level
     */
    public static List<Integer> DFSCommonNLevels(GraphFile g, int v1, int v2, int level)
    {
	List<Integer> list1 = traverseNLevels(g, v1, level);
	list1 = Driver.removeDuplicatesAndSort(list1);
	List<Integer> list2 = traverseNLevels(g, v2, level);
	list2 = Driver.removeDuplicatesAndSort(list2);

	// to iterate
	ListIterator<Integer> l1 = list1.listIterator();
	ListIterator<Integer> l2 = list2.listIterator();

	List<Integer> inCommon = new LinkedList<Integer>();

	int l1val = l1.next();
	int l2val = l2.next();

	while (l1.hasNext() && l2.hasNext())
	{// go until the end of a list
	    if (l1val == l2val)
	    {
		inCommon.add(l1val);
		l1val = l1.next();
		l2val = l2.next();
	    }
	    else if (l1val > l2val)
	    {
		l2val = l2.next();
	    }
	    else
	    {
		l1val = l1.next();
	    }
	}

	return inCommon;
    }

    /**
     * This function uses dfs to find a path from startPage to endPage
     * 
     * @param startPage
     *            Starting page number
     * @param endPage
     *            Ending page number
     * @return true if path found, false if not
     */
    public static boolean findPath(final GraphFile graph, final int startPage, final int endPage)
    {
	if (g == null)
	    return false;

	g = graph;
	marked = new HashMap<Integer, Boolean>();
	edgeTo = new HashMap<Integer, Integer>();
	return dfsFindPath(startPage, endPage);
    }

    private static boolean dfsFindPath(final int startPage, final int endPage)
    {
	if (startPage == endPage)
	    return true;
	marked.put(startPage, true);
	System.out.println(g.getPageName(startPage));
	for (int w : g.getOutgoingLinks(startPage))
	{
	    if (!marked.containsKey(w))
	    {
		edgeTo.put(w, startPage);
		if (dfsFindPath(w, endPage))
		    return true;
	    }
	}
	return false;
    }

    /**
     * This function will perform a depth first traversal starting from pageNum. It is a wrapper method for dfsTraversal().
     * 
     * @param pageNum
     *            Page to start traversal from.
     */
    public static void traverse(final GraphFile graph, final int pageNum)
    {
	g = graph;
	marked = new HashMap<Integer, Boolean>();
	edgeTo = new HashMap<Integer, Integer>();
	dfsTraversal(pageNum);
    }

    private static void dfsTraversal(final int pageNum)
    {
	marked.put(pageNum, true);
	System.out.println(g.getPageName(pageNum));
	for (int w : g.getOutgoingLinks(pageNum))
	{
	    if (!marked.containsKey(w))
	    {
		edgeTo.put(w, pageNum);
		dfsTraversal(w);
	    }
	}
    }

    private static LinkedList<Integer> pages;

    /**
     * This function will perform a depth first traversal starting from pageNum only to the nth level.
     * 
     * @param graph
     *            GraphFile object
     * @param pageNum
     *            Starting page
     * @param n
     *            Level to stop at
     * @return LinkedList of pages found at nth level
     */
    public static LinkedList<Integer> traverseNLevels(final GraphFile graph, final int pageNum,
	    final int n)
    {
	g = graph;
	pages = new LinkedList<Integer>();
	dfsTraversalNLevels(pageNum, n, 0);

	Driver.removeDuplicatesAndSort(pages);
	return pages;
    }

    private static void dfsTraversalNLevels(final int pageNum, final int n, int level)
    {
	if (n == level)
	{
	    pages.add(pageNum);
	    return;
	}
	level++;
	// System.out.println(g.getPageName(pageNum) + ", level: " + level);
	for (int w : g.getOutgoingLinks(pageNum))
	{
	    dfsTraversalNLevels(w, n, level);
	}
    }

}
